package Arithmetic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 34255
 * Date: 2024-10-20
 * Time: 22:49
 */
//双指针
public class DoublePointer {
    //1089.复写零

    /**
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * @param arr 目标数组
     */
    public static void duplicateZeros(int[] arr) {
        //定义双指针
        int cur = 0;
        int dest = -1;
        //先查找最后一个需要进行判断复写的元素下标位置
        while(true){
            //判断移动1步还是2步
            if(arr[cur] == 0){
                dest+=2;
            }else{
                dest++;
            }
            //判断是否到达元素最后一个位置
            if(dest >= arr.length - 1){
                break;
            }
            cur++;
        }

        //判断dest是否因为越界
        if(dest == arr.length){
            arr[arr.length - 1] = 0;
            dest-=2;
            cur--;
        }

        //从右往左复写零
        while(cur > -1){
            if(arr[cur] == 0){
                arr[dest - 1] = arr[dest] = 0;
                dest-=2;
                cur--;
            }else{
                arr[dest--] = arr[cur--];
            }
        }
    }

    //11.盛水最多的容器

    /**
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * @param arr 目标数组
     * @return 最大盛水面积
     */
    public static int maxArea(int[] arr) {
        //定义双指针
        int left = 0;
        int right =arr.length - 1;
        int maxArea = 0;
        while(left <= right){
            //计算盛水面积，并更新最大盛水面积
            maxArea = Math.max(maxArea,Math.min(arr[left],arr[right]) * (right - left));
            //判断大小，决定哪个指针移动
            if(arr[left] <= arr[right]){
                left++;
            }else{
                right--;
            }
        }
        return maxArea;
    }

    //611.有效的三角形个数

    /**
     * 时间复杂度：O(NlogN + N*2)
     * 空间复杂度：O(1)
     * @param nums 目标数组
     * @return 有效三角形的个数
     */
    public static int triangleNumber(int[] nums) {
        //对数组排序
        Arrays.sort(nums);

        int count = 0;//记录有效个数
        int S = nums.length - 1;

        while(S >= 2){
            int left = 0;
            int right = S - 1;
            while(left < right){
                if(nums[left] + nums[right] > nums[S]){
                    count += right - left;
                    right--;
                }else{
                    left++;
                }
            }
            S--;
        }
        return count;
    }

    //LCR 179.查找总价格为目标值的两个商品

    /**
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * @param price
     * @param target
     * @return
     */
    public static int[] twoSum(int[] price, int target) {
        //定义双指针
        int left = 0;
        int right = price.length - 1;
        while(left < right){
            if(price[left] + price[right] > target){
                right--;
            }else if(price[left] + price[right] < target){
                left++;
            }else{
                return new int[]{price[left],price[right]};
            }
        }
        return null;
    }

    //15.三数之和

    /**
     * 时间复杂度：O(logN + N * 2)
     * 空间复杂度：O(1)
     * @param nums 目标数组
     * @return 符合条件的三元数组
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        //数组排序
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();
        //定义S指针
        int S = nums.length - 1;
        while(S >= 2){
            int left = 0;
            int right = S - 1;
            int target = -nums[S];
            //在[left,right]区间寻找所有和为S的二元数组
            while(left < right && target <= 0){//优化次数
                if(nums[left] + nums[right] > target){
                    right--;
                }else if(nums[left] + nums[right] < target){
                    left++;
                }else{//添加元素
                    ret.add(new ArrayList<>(Arrays.asList(nums[left],nums[right],nums[S])));
                    right--;
                    left++;
                    //去重操作
                    while(left < right && nums[right] == nums[right + 1]) right--;
                    while(left < right && nums[left] == nums[left - 1]) left++;
                }
            }
            while(-target == nums[S] && S > 1) S--;//防止数组越界
        }
        return ret;
    }

    //18.四数之和

    /**
     * 时间复杂度：O(N * 3)
     * 空间复杂度：O(N)
     * @param nums 目标数组
     * @param target 目标值
     * @return 符合情况的不重复四元组
     */
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        //排序
        Arrays.sort(nums);

        List<List<Integer>> list = new ArrayList<>();
        int S = 0;
        while(S < nums.length - 3){
            int cur = S + 1;
            while(cur < nums.length - 2){
                //防止超出int表示范围
                long sum = target;
                sum -= (nums[S] + nums[cur]);
                int left = cur + 1;
                int right = nums.length - 1;
                while(left < right){
                    if(nums[left] + nums[right] > sum){
                        right--;
                    }else if(nums[left] + nums[right] < sum){
                        left++;
                    }else{
                        list.add(new ArrayList<>(Arrays.asList(nums[S],nums[cur],nums[left],nums[right])));
                        //缩小区间
                        left++;
                        right--;
                        //去重操作
                        while(left < right && nums[left] == nums[left - 1]) left++;
                        while(left < right && nums[right] == nums[right + 1]) right--;
                    }
                }
                cur++;//缩小区间
                while(cur < nums.length - 2 && nums[cur] == nums[cur - 1]) cur++;//去重操作
            }
            S++;//缩小区间
            while(S < nums.length - 3 && nums[S] == nums[S - 1]) S++;//去重操作
        }
        return list;
    }

    //202.快乐数

    /**
     *
     * @param n 目标数
     * @return 是否为快乐数
     */
    public static boolean isHappy(int n) {
        //定义快慢指针
        int slow = calculate(n);
        int fast = calculate(slow);
        while(slow != fast){
            slow = calculate(slow);
            fast = calculate(fast);
            fast = calculate(fast);
        }
        return slow == 1;
    }

    public static int calculate(int n){
        String str = String.valueOf(n);
        int sum = 0;
        for (int i = 0; i < str.length(); i++) {
            Integer ret = Integer.valueOf(str.charAt(i) + "");
            sum += ret * ret;
        }
        return sum;
    }
    public static void main(String[] args) {
        //1089.复写零
        int[] array1 = {0,0,0,0,0,0,0};
        duplicateZeros(array1);
        System.out.println(Arrays.toString(array1));

        //11.盛水最多的容器
        int[] array2 = {1,8,6,2,5,4,8,3,7};
        int ret = maxArea(array2);
        System.out.println(ret);

        //611.有效的三角形个数
        int[] array3 = {4,2,3,4};
        int count = triangleNumber(array3);
        System.out.println(count);

        //LCR 179.查找总价格为目标值的两个商品
        int[] array4 = {8, 21, 27, 34, 52, 66};
        int[] arr = twoSum(array4,18);
        System.out.println(Arrays.toString(arr));

        //15.三数之和
        int[] array5 = {-1,0,1,2,-1,-4};
        List<List<Integer>> list1 = threeSum(array5);
        System.out.println(list1);

        //18.四数之和
        int[] array6 = {1000000000,1000000000,1000000000,1000000000};
        List<List<Integer>> list2 = fourSum(array6,-294967296);
        System.out.println(list2);

        //202.快乐数
        boolean ret1 = isHappy(2);
        System.out.println(ret1);
    }
}
